<!DOCTYPE HTML>
<html lang="zh-CN" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title> Section 4.2 - PurpleDragonBookAnswer</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="Purple Dragon Book Answer Online Edition">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../preface.html"><strong aria-hidden="true">1.</strong> Preface</a></li><li class="chapter-item expanded "><a href="../../ch01/ch01.html"><strong aria-hidden="true">2.</strong> Chapter 1</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch01/1.1/1.1.html"><strong aria-hidden="true">2.1.</strong> Section 1.1</a></li><li class="chapter-item expanded "><a href="../../ch01/1.3/1.3.html"><strong aria-hidden="true">2.2.</strong> Section 1.3</a></li><li class="chapter-item expanded "><a href="../../ch01/1.6/1.6.html"><strong aria-hidden="true">2.3.</strong> Section 1.6</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch02/ch02.html"><strong aria-hidden="true">3.</strong> Chapter 2</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch02/key-point/key-point.html"><strong aria-hidden="true">3.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch02/2.2/2.2.html"><strong aria-hidden="true">3.2.</strong> Section 2.2</a></li><li class="chapter-item expanded "><a href="../../ch02/2.3/2.3.html"><strong aria-hidden="true">3.3.</strong> Section 2.3</a></li><li class="chapter-item expanded "><a href="../../ch02/2.4/2.4.html"><strong aria-hidden="true">3.4.</strong> Section 2.4</a></li><li class="chapter-item expanded "><a href="../../ch02/2.6/2.6.html"><strong aria-hidden="true">3.5.</strong> Section 2.6</a></li><li class="chapter-item expanded "><a href="../../ch02/2.8/2.8.html"><strong aria-hidden="true">3.6.</strong> Section 2.8</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch03/ch03.html"><strong aria-hidden="true">4.</strong> Chapter 3</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch03/key-point/key-point.html"><strong aria-hidden="true">4.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch03/3.1/3.1.html"><strong aria-hidden="true">4.2.</strong> Section 3.1</a></li><li class="chapter-item expanded "><a href="../../ch03/3.3/3.3.html"><strong aria-hidden="true">4.3.</strong> Section 3.3</a></li><li class="chapter-item expanded "><a href="../../ch03/3.4/3.4.html"><strong aria-hidden="true">4.4.</strong> Section 3.4</a></li><li class="chapter-item expanded "><a href="../../ch03/3.5/3.5.html"><strong aria-hidden="true">4.5.</strong> Section 3.5</a></li><li class="chapter-item expanded "><a href="../../ch03/3.6/3.6.html"><strong aria-hidden="true">4.6.</strong> Section 3.6</a></li><li class="chapter-item expanded "><a href="../../ch03/3.7/3.7.html"><strong aria-hidden="true">4.7.</strong> Section 3.7</a></li><li class="chapter-item expanded "><a href="../../ch03/3.8/3.8.html"><strong aria-hidden="true">4.8.</strong> Section 3.8</a></li><li class="chapter-item expanded "><a href="../../ch03/3.9/3.9.html"><strong aria-hidden="true">4.9.</strong> Section 3.9</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch04/ch04.html"><strong aria-hidden="true">5.</strong> Chapter 4</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch04/key-point/key-point.html"><strong aria-hidden="true">5.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch04/4.2/4.2.html" class="active"><strong aria-hidden="true">5.2.</strong> Section 4.2</a></li><li class="chapter-item expanded "><a href="../../ch04/4.3/4.3.html"><strong aria-hidden="true">5.3.</strong> Section 4.3</a></li><li class="chapter-item expanded "><a href="../../ch04/4.4/4.4.html"><strong aria-hidden="true">5.4.</strong> Section 4.4</a></li><li class="chapter-item expanded "><a href="../../ch04/4.5/4.5.html"><strong aria-hidden="true">5.5.</strong> Section 4.5</a></li><li class="chapter-item expanded "><a href="../../ch04/4.6/4.6.html"><strong aria-hidden="true">5.6.</strong> Section 4.6</a></li><li class="chapter-item expanded "><a href="../../ch04/4.7/4.7.html"><strong aria-hidden="true">5.7.</strong> Section 4.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch05/ch05.html"><strong aria-hidden="true">6.</strong> Chapter 5</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch05/5.1/5.1.html"><strong aria-hidden="true">6.1.</strong> Section 5.1</a></li><li class="chapter-item expanded "><a href="../../ch05/5.2/5.2.html"><strong aria-hidden="true">6.2.</strong> Section 5.2</a></li><li class="chapter-item expanded "><a href="../../ch05/5.3/5.3.html"><strong aria-hidden="true">6.3.</strong> Section 5.3</a></li><li class="chapter-item expanded "><a href="../../ch05/5.4/5.4.html"><strong aria-hidden="true">6.4.</strong> Section 5.4</a></li><li class="chapter-item expanded "><a href="../../ch05/5.5/5.5.html"><strong aria-hidden="true">6.5.</strong> Section 5.5</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch06/ch06.html"><strong aria-hidden="true">7.</strong> Chapter 6</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch06/6.1/6.1.html"><strong aria-hidden="true">7.1.</strong> Section 6.1</a></li><li class="chapter-item expanded "><a href="../../ch06/6.2/6.2.html"><strong aria-hidden="true">7.2.</strong> Section 6.2</a></li><li class="chapter-item expanded "><a href="../../ch06/6.3/6.3.html"><strong aria-hidden="true">7.3.</strong> Section 6.3</a></li><li class="chapter-item expanded "><a href="../../ch06/6.4/6.4.html"><strong aria-hidden="true">7.4.</strong> Section 6.4</a></li><li class="chapter-item expanded "><a href="../../ch06/6.5/6.5.html"><strong aria-hidden="true">7.5.</strong> Section 6.5</a></li><li class="chapter-item expanded "><a href="../../ch06/6.6/6.6.html"><strong aria-hidden="true">7.6.</strong> Section 6.6</a></li><li class="chapter-item expanded "><a href="../../ch06/6.7/6.7.html"><strong aria-hidden="true">7.7.</strong> Section 6.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch07/ch07.html"><strong aria-hidden="true">8.</strong> Chapter 7</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch07/7.2/7.2.html"><strong aria-hidden="true">8.1.</strong> Section 7.2</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.3.html"><strong aria-hidden="true">8.2.</strong> Section 7.3</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.4.html"><strong aria-hidden="true">8.3.</strong> Section 7.4</a></li><li class="chapter-item expanded "><a href="../../ch07/7.5/7.5.html"><strong aria-hidden="true">8.4.</strong> Section 7.5</a></li><li class="chapter-item expanded "><a href="../../ch07/7.6/7.6.html"><strong aria-hidden="true">8.5.</strong> Section 7.6</a></li><li class="chapter-item expanded "><a href="../../ch07/7.7/7.7.html"><strong aria-hidden="true">8.6.</strong> Section 7.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch08/ch08.html"><strong aria-hidden="true">9.</strong> Chapter 8</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch08/8.2/8.2.html"><strong aria-hidden="true">9.1.</strong> Section 8.2</a></li><li class="chapter-item expanded "><a href="../../ch08/8.3/8.3.html"><strong aria-hidden="true">9.2.</strong> Section 8.3</a></li><li class="chapter-item expanded "><a href="../../ch08/8.4/8.4.html"><strong aria-hidden="true">9.3.</strong> Section 8.4</a></li><li class="chapter-item expanded "><a href="../../ch08/8.5/8.5.html"><strong aria-hidden="true">9.4.</strong> Section 8.5</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">PurpleDragonBookAnswer</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="exercises-for-section-42"><a class="header" href="#exercises-for-section-42">Exercises for Section 4.2</a></h1>
<h3 id="421"><a class="header" href="#421">4.2.1</a></h3>
<p>Consider the context-free grammar:</p>
<pre><code>S -&gt; S S + | S S * | a
</code></pre>
<p>and the string aa + a*.</p>
<ol>
<li>Give a leftmost derivation for the string.</li>
<li>Give a rightmost derivation for the string.</li>
<li>Give a parse tree for the string.</li>
<li>! Is the grammar ambiguous or unambiguous? Justify your answer.</li>
<li>! Describe the language generated by this grammar.</li>
</ol>
<h4 id="answer"><a class="header" href="#answer">Answer</a></h4>
<ol>
<li>S =lm=&gt; SS* =&gt; SS+S* =&gt; aS+S* =&gt; aa+S* =&gt; aa+a*</li>
<li>S =rm=&gt; SS* =&gt; Sa* =&gt; SS+a* =&gt; Sa+a* =&gt; aa+a*</li>
<li></li>
</ol>
<pre><code>![4 2 1](./assets/4.2.1.gif)
</code></pre>
<ol start="4">
<li>Unambiguous</li>
<li>The set of all postfix expressions consist of addition and multiplication</li>
</ol>
<h3 id="422"><a class="header" href="#422">4.2.2</a></h3>
<p>Repeat Exercise 4 . 2 . 1 for each of the following grammars and strings:</p>
<ol>
<li>
<p>S -&gt; 0 S 1 | 0 1 with string 00011l.</p>
</li>
<li>
<p>S -&gt; + S S | * S S | a with string + * aaa.</p>
</li>
<li>
<p>! S -&gt; S (S) S | ε with string (()())</p>
</li>
<li>
<p>! S -&gt; S + S | S S | (S) | S * | a with string (a+a)*a</p>
</li>
<li>
<p>! S -&gt; (L) | a 以及 L -&gt; L, S | S with string ((a,a),a,(a))</p>
</li>
<li>
<p>!! S -&gt; a S b S | b S a S | ε with string aabbab</p>
</li>
<li>
<p>The following grammar for boolean expressions:</p>
<pre><code>bexpr -&gt; bexpr or bterm | bterm
bterm -&gt; bterm and bfactor | bfactor
bfactor -&gt; not bfactor | (bexpr) | true | false
</code></pre>
</li>
</ol>
<h4 id="answer-1"><a class="header" href="#answer-1">Answer</a></h4>
<ol>
<li>S =lm=&gt; 0S1 =&gt; 00S11 =&gt; 000111</li>
<li>S =rm=&gt; 0S1 =&gt; 00S11 =&gt; 000111</li>
<li>Omit</li>
<li>Unambiguous</li>
<li>The set of all strings of 0s and followed by an equal number of 1s</li>
</ol>
<p>2、</p>
<ol>
<li>S =lm=&gt; +SS =&gt; +*SSS =&gt; +*aSS =&gt; +*aaS =&gt; +*aaa</li>
<li>S =rm=&gt; +SS =&gt; +Sa =&gt; +*SSa =&gt; +*Saa =&gt; +*aaa</li>
<li>Omit</li>
<li>Unambiguous</li>
<li>The set of all prefix expressions consist of addition and multiplication.</li>
</ol>
<p>3、</p>
<ol>
<li>S =lm=&gt; S(S)S =&gt; (S)S =&gt; (S(S)S)S =&gt; ((S)S)S =&gt; (()S)S =&gt; (()S(S)S)S =&gt; (()(S)S)S =&gt; (()()S)S =&gt; (()())S =&gt; (()())</li>
<li>S =rm=&gt; S(S)S =&gt; S(S) =&gt; S(S(S)S) =&gt; S(S(S)) =&gt; S(S()) =&gt; S(S(S)S()) =&gt; S(S(S)()) =&gt; S(S()()) =&gt; S(()()) =&gt; (()())</li>
<li>Omit</li>
<li>Ambiguous</li>
<li>The set of all strings of symmetrical parentheses</li>
</ol>
<p>4、</p>
<ol>
<li>S =lm=&gt; SS =&gt; S*S =&gt; (S)*S =&gt; (S+S)*S =&gt; (a+S)*S =&gt; (a+a)*S =&gt; (a+a)*a</li>
<li>S =rm=&gt; SS =&gt; Sa =&gt; S*a =&gt; (S)*a =&gt; (S+S)*a =&gt; (S+a)*a =&gt; (a+a)*a</li>
<li>Omit</li>
<li>Ambiguous</li>
<li>The set of all string of plus, mupplication, 'a' and symmetrical parentheses, and plus is not the beginning and end of the position, multiplication is not the beginning of the position</li>
</ol>
<p>5、</p>
<ol>
<li>S =lm=&gt; (L) =&gt; (L, S) =&gt; (L, S, S) =&gt; ((S), S, S) =&gt; ((L), S, S) =&gt; ((L, S), S, S) =&gt; ((S, S), S, S) =&gt; ((a, S), S, S) =&gt; ((a, a), S, S) =&gt; ((a, a), a, S) =&gt; ((a, a), a, (L)) =&gt; ((a, a), a, (S)) =&gt; ((a, a), a, (a))</li>
<li>S =rm=&gt; (L) =&gt; (L, S) =&gt; (L, (L)) =&gt; (L, (a)) =&gt; (L, S, (a)) =&gt; (L, a, (a)) =&gt; (S, a, (a)) =&gt; ((L), a, (a)) =&gt; ((L, S), a, (a)) =&gt; ((S, S), a, (a)) =&gt; ((S, a), a, (a)) =&gt; ((a, a), a, (a))</li>
<li>Omit</li>
<li>Unambiguous</li>
<li>Something like tuple in Python</li>
</ol>
<p>6、</p>
<ol>
<li>S =lm=&gt; aSbS =&gt; aaSbSbS =&gt; aabSbS =&gt; aabbS =&gt; aabbaSbS =&gt; aabbabS =&gt; aabbab</li>
<li>S =rm=&gt; aSbS =&gt; aSbaSbS =&gt; aSbaSb =&gt; aSbab =&gt; aaSbSbab =&gt; aaSbbab =&gt; aabbab</li>
<li>Omit</li>
<li>Ambiguous</li>
<li>The set of all strings of 'a's and 'b's of the equal number of 'a's and 'b's</li>
</ol>
<p>7、 Unambiguous, boolean expression</p>
<h3 id="423"><a class="header" href="#423">4.2.3</a></h3>
<p>Design grammars for the following languages:</p>
<ol>
<li>The set of all strings of 0s and 1s such that every 0 is immediately followed
by at least one 1.</li>
<li>! The set of all strings of 0s and 1s that are palindromes; that is, the string
reads the same backward as forward.</li>
<li>! The set of all strings of 0s and 1s with an equal number of 0s and 1s.</li>
<li>!! The set of all strings of 0s and 1s with an unequal number of 0s and 1s.</li>
<li>! The set of all strings of 0s and as in which 011 does not appear as a
substring.</li>
<li>!! The set of all strings of 0s and 1s of the form xy, where x&lt;&gt;y and x and y are of the same length.</li>
</ol>
<h4 id="answer-2"><a class="header" href="#answer-2">Answer</a></h4>
<p>1、</p>
<pre><code>S -&gt; (0?1)*
</code></pre>
<p>2、</p>
<pre><code>S -&gt; 0S0 | 1S1 | 0 | 1 | ε
</code></pre>
<p>3、</p>
<pre><code>S -&gt; 0S1S | 1S0S | ε
</code></pre>
<p>5、</p>
<pre><code>S -&gt; 1*(0+1?)*
</code></pre>
<h3 id="424"><a class="header" href="#424">4.2.4</a></h3>
<p>There is an extended grammar notation in common use.
In this notation, square and curly braces in production bodies are metasymbols
(like -&gt; or |) with the following meanings:</p>
<ol>
<li>Square braces around a grammar symbol or symbols denotes that these
constructs are optional. Thus, production A -&gt; X[Y]Z has the same
effect as the two productions A -&gt; XYZ and A -&gt; XZ.</li>
<li>Curly braces around a grammar symbol or symbols says that these sym­bols
may be repeated any number of times, including zero times. Thus,
A -&gt; X{YZ} has the same effect as the infinite sequence of productions
A -&gt; X, A -&gt; XYZ, A -&gt; XYZYZ, and so on.</li>
</ol>
<p>Show that these two extensions do not add power to grammars; that is, any
language that can be generated by a grammar with these extensions can be
generated by a grammar without the extensions.</p>
<h4 id="proof"><a class="header" href="#proof">Proof</a></h4>
<table>
    <thead>
        <tr>
            <th>extended grammar</th>
            <th>not extended grammar</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>A -> X[Y]Z</td>
            <td>A -> XZ | XYZ</td>
        </tr>
        <tr>
            <td>A -> X{YZ}</td>
            <td>A -> XB<br/>B -> YZB | ε</td>
        </tr>
    </tbody>
</table>
<h3 id="425"><a class="header" href="#425">4.2.5</a></h3>
<p>Use the braces described in Exercise 4.2.4 to simplify the
following grammar for statement blocks and conditional statements:</p>
<pre><code>stmt -&gt; if expr then stmt else stmt
      | if stmt them stmt
      | begin stmtList end
stmtList -&gt; stmt; stmtList | stmt
</code></pre>
<h4 id="answer-3"><a class="header" href="#answer-3">Answer</a></h4>
<pre><code>stmt -&gt; if expr then stmt [else stmt]
      | begin stmtList end
stmtList -&gt; stmt [; stmtList]
</code></pre>
<h3 id="426"><a class="header" href="#426">4.2.6</a></h3>
<p>Extend the idea of Exercise 4.2.4 to allow any regular expres­sion
of grammar symbols in the body of a production. Show that this extension
does not allow grammars to define any new languages.</p>
<h4 id="proof-1"><a class="header" href="#proof-1">Proof</a></h4>
<p>Every regular grammar has a corresponding not extended grammar</p>
<h3 id="427-"><a class="header" href="#427-">4.2.7 !</a></h3>
<p>A grammar symbol X (terminal or nonterminal) is useless if
there is no derivation of the form S =*=&gt; wXy =*=&gt; wxy. That is, X can never
appear in the derivation of any sentence.</p>
<ol>
<li>
<p>Give an algorithm to eliminate from a grammar all productions containing useless symbols.</p>
</li>
<li>
<p>Apply your algorithm to the grammar:</p>
<pre><code>S -&gt; 0 | A
A -&gt; AB
B -&gt; 1
</code></pre>
</li>
</ol>
<h3 id="428"><a class="header" href="#428">4.2.8</a></h3>
<p>The grammar in Fig. 4.7 generates declarations for a sin­gle
numerical identifier; these declarations involve four different, independent
properties of numbers.</p>
<pre><code>stmt -&gt; declare id optionList
optionList -&gt; optionList option | ε
option -&gt; mode | scale | precision | base
mode -&gt; real | complex
scale -&gt; fixed | floating
precision -&gt; single | double
base -&gt; binary | decimal
</code></pre>
<ol>
<li>
<p>Generalize the grammar of Fig. 4.7 by allowing n options Ai, for some
fixed n and for i = 1,2... ,n, where Ai can be either ai or bi· Your
grammar should use only 0(n) grammar symbols and have a total length
of productions that is O(n).</p>
</li>
<li>
<p>! The grammar of Fig. 4.7 and its generalization in part (a) allow declarations
that are contradictory and/or redundant, such as</p>
<p>declare foo real fixed real floating</p>
<p>We could insist that the syntax of the language forbid such declarations;
that is, every declaration generated by the grammar has exactly one value
for each of the n options. If we do, then for any fixed n there is only a finite
number of legal declarations. The language of legal declarations thus has
a grammar (and also a regular expression), as any finite language does.
The obvious grammar, in which the start symbol has a production for
every legal declaration has n! productions and a total production length
of O(n x n!). You must do better: a total production length that is O(n2^n)</p>
</li>
<li>
<p>!! Show that any grammar for part (b) must have a total production length of at least 2n.</p>
</li>
<li>
<p>What does part (c) say about the feasibility of enforcing nonredundancy
and noncontradiction among options in declarations via the syntax of the programming language?</p>
</li>
</ol>
<h4 id="answer-4"><a class="header" href="#answer-4">Answer</a></h4>
<p>1、</p>
<pre><code>stmt -&gt; declare id optionList
optionList -&gt; optionList option | ε
option -&gt; A_1 | A_2 | … | A_n
A_1 -&gt; a_1 | b_1
A_2 -&gt; a_2 | b_2
…
A_n -&gt; a_n | b_n
</code></pre>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../ch04/key-point/key-point.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../ch04/4.3/4.3.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../ch04/key-point/key-point.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../ch04/4.3/4.3.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
